home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 1 / LSD Compendium Deluxe 1.iso / a / programming / assembly / pointinpolygonproblem.lha / PointInPolygonProblem.s < prev   
Encoding:
Text File  |  1994-01-03  |  10.0 KB  |  413 lines
  1. *****************************************************************************
  2. *** Point in Polygon Routine           (c) November 1991 by McDeal/D-TECT ***
  3. *** Released in HACK-MAG Issue #7                      ***
  4. *****************************************************************************
  5.  
  6. ;With this routine you can test whether a point is within a convex polygon
  7. ;or not.
  8.  
  9. ;This formula was used:    C = (x2-x1)*(y-y1)-(y2-y1)*(x-x1)
  10. ;when C<0, then the point P(x,y) is left of the line (x1,y1,x2,y2)
  11. ;when C>0, then the point P(x,y) is right of the line (x1,y1,x2,y2)
  12.  
  13. ;The result of this formula is only correct if your coordinate origin is
  14. ;in the upper left corner of the screen. If it is in the lower left corner
  15. ;you have to interprete the result the other way round...
  16.  
  17. ;IMPORTANT NOTE: I didn't optimize anything of this example because I was
  18. ;in a BIG hurry! And I think it is much easier for beginners to understand
  19. ;source codes which aren't optimized... You know...
  20.  
  21. ;                        signed: McDeal/D-TECT
  22.  
  23. ;PS: GREEN means: Inside polygon.
  24. ;    RED means: Outside polygon.   Now start it!
  25.  
  26. ;PPS: This is a Devpac Source Code!
  27.  
  28. ***************************************************
  29. *** Constants Definition            ***
  30. ***************************************************
  31.  
  32. PlaneWidth    = 40
  33. PlaneLen    = PlaneWidth*256
  34. SpriteHigh      = 1
  35. SpriteWidth     = 16
  36.  
  37. MouseClipX      = 320-SpriteWidth+1
  38. MouseClipY      = 256-SpriteHigh-5
  39.  
  40. DL_MInterns    = $ca
  41. SML        = 0
  42.  
  43. ***************************************************
  44. *** Program Start                ***
  45. ***************************************************
  46.  
  47.         opt    o+
  48.  
  49.         section    a,code_c
  50.  
  51. Start:        lea    $dff000,a5
  52.  
  53.         bsr     DrawPolygon
  54.         bsr.s    InitInts
  55.         bsr.s    InitSprite
  56.         bsr.s    SetPlanePtr
  57.         bsr    StartCopper
  58.         bsr    Main
  59.         bsr    StopCopper
  60.         bsr.s    ReInitInts
  61.  
  62.         moveq    #0,d0
  63.         rts
  64.  
  65. ***************************************************
  66. *** Init Interrupt                ***
  67. ***************************************************
  68.  
  69. InitInts:    move.w    $1c(a5),d0        ;Save INTENA
  70.         bset    #15,d0
  71.         move.w    d0,Interrupts
  72.         move.w    #$3fff,$9a(a5)        ;turn off all Ints (INTENA)
  73.         move.l    $6c.w,Level3Int        ;Save old Level 3 Int
  74.         lea    MouseRoutine(pc),a0    ;Set New Routine Ptr
  75.         move.l    a0,$6c.w
  76.         move.w    #$c020,$9a(a5)        ;Permit Level 3 Int
  77.         rts
  78.  
  79. Interrupts:    dc.w    0
  80. Level3Int:    dc.l    0
  81.  
  82. ***************************************************
  83. *** ReInit Interrupts                ***
  84. ***************************************************
  85.  
  86. ReInitInts:    move.w    #$3fff,$9a(a5)        ;turn off all Ints (INTENA)
  87.         move.l    Level3Int(pc),$6c.w    ;set old Level3Int Ptr
  88.         move.w    Interrupts(pc),$9a(a5)    ;set old INTENA contents
  89.         rts
  90.  
  91. ***************************************************
  92. *** Init Sprite                    ***
  93. ***************************************************
  94.  
  95. InitSprite:    move.l    #MouseSpr,d0        ;Sprite Structure Ptr
  96.         lea    MouseSprite(pc),a0    ;NCList Ptr
  97.         move.w    d0,6(a0)        ;Set Ptr
  98.         swap    d0
  99.         move.w    d0,2(a0)
  100.         rts
  101.  
  102. ***************************************************
  103. *** Set Plane Ptr in Copperlist            ***
  104. ***************************************************
  105.  
  106. SetPlanePtr:    lea    PlanePtr(pc),a1
  107.         move.l    #Plane,d0
  108.         move.w    d0,6(a1)        ;Low Word
  109.         swap    d0
  110.         move.w    d0,2(a1)        ;High Word
  111.         rts
  112.  
  113. ***************************************************
  114. *** Start/Stop Copper                ***
  115. ***************************************************
  116.  
  117. StartCopper:    move.w    #$0380,$96(a5)
  118.         move.l    #NCList,$84(a5)
  119.         clr.w    $8a(a5)
  120.         move.w    #$83a0,$96(a5)
  121.         clr.w    $36(a5)            ;Clear JOY0DAT
  122.         rts
  123.  
  124. StopCopper:    move.w    #$0380,$96(a5)
  125.         clr.w    $88(a5)
  126.         move.w    #$8380,$96(a5)
  127.         rts
  128.  
  129. ***************************************************
  130. *** Draw Polygon                ***
  131. ***************************************************
  132.  
  133. DrawPolygon:    lea    $dff002,a6
  134.         lea    Koords(pc),a2
  135.         move.w    (a2)+,d7        ;Number of Lines
  136.  
  137. .DrawLineLoop:    lea    Plane,a0
  138.         moveq    #PlaneWidth,d4        ;This shitty loop isn't
  139.         moveq    #-1,d5            ;optimized!!! Don't blame me!
  140.         movem.w    (a2)+,d0-d3
  141.  
  142. .WB:        btst    #6,(a6)
  143.         bne.s    .WB
  144.         move.w    d5,$44-$02(a6)
  145.         move.w    d5,$72-$02(a6)
  146.         move.w    #$8000,$74-$02(a6)
  147.         move.w    d4,$60-$02(a6)
  148.         move.w    d4,$66-$02(a6)
  149.  
  150.         bsr.s    DrawLine
  151.         dbf    d7,.DrawLineLoop
  152.         rts
  153.  
  154. ***************************************************
  155. *** DrawLine                    ***
  156. ***************************************************
  157.  
  158. ;Needs:
  159. ; a0    PlanePtr
  160. ; a6    $dff002
  161. ; d0/d1 x,y start pos
  162. ; d2/d3 x,y end   pos
  163. ; d4    Width of plane
  164.  
  165. ;Kills:
  166. ; d0-d4/a0-a1 (+d5 in Fill Mode)
  167.  
  168. DrawLine:    cmp.w    d1,d3            ;drawing only from top to bottom is
  169.         bge.s    .y1ly2            ;necessary for:
  170.         exg    d0,d2            ;a: up-down differences (same koords)
  171.         exg    d1,d3            ;b: blitter invert bit (only at top of line)
  172.  
  173. .y1ly2:        sub.w    d1,d3            ;d3:yd
  174.  
  175. ;here we could do an optimization with special shifts
  176. ;depending on the PlaneWidth value ... i know it, but please, let it be.
  177.  
  178.         mulu    d4,d1            ;use muls for neg y-vals
  179.         add.l    d1,a0            ;please don't use add.w here!
  180.         moveq    #0,d1            ;d1:quant-counter
  181.         sub.w    d0,d2            ;d2:xd
  182.         bge.s    .xdpos
  183.         addq.w    #2,d1            ;set bit 1 of quant-counter (here it could be a moveq)
  184.         neg.w    d2
  185. .xdpos:        moveq    #$f,d4            ;d4 full cleaned (for later oktants move.b)
  186.         and.w    d0,d4
  187.         lsr.w    #3,d0            ;yeah, on byte (necessary for bchg) ....
  188.         add.w    d0,a0            ;... blitter ands automagically
  189.         ror.w    #4,d4            ;4:shift
  190.         or.w    #$b00+DL_MInterns,d4    ;bltcon0-codes
  191.         swap    d4
  192.         cmp.w    d2,d3            ;which delta is the biggest?
  193.         bge.s    .dygdx
  194.         addq.w    #1,d1            ;set bit 0 of quant-counter
  195.         exg    d2,d3            ;exchange xd with yd
  196. .dygdx:        add.w    d2,d2            ;d2:xd*2
  197.         move.w    d2,d0            ;d0:save for $52(a6)
  198.         sub.w    d3,d0            ;d0:xd*2-yd
  199.         addx.w    d1,d1            ;Bit0:sign-bit
  200.         move.b    .oktants(pc,d1.w),d4    ;in low byte of d4 (upper byte cleaned above)
  201.         swap    d2
  202.         move.w    d0,d2
  203.         sub.w    d3,d2            ;d2:2*(xd-yd)
  204.         moveq    #6,d1            ;d1:shiftval(not necessary) + testval for the blitter
  205.         lsl.w    d1,d3            ;d3:BLTSIZE
  206.         add.w    #$42,d3
  207.         lea    $52-2(a6),a1        ;a1:CUSTOM + $52
  208.  
  209. ;WARNING:  if you use fastmem and an extreme DMA-Access (e.g.  6
  210. ;planes and copper), you should insert a tst.b (a6) here (for the
  211. ;shitty AGNUS-BUG).
  212.  
  213. .WB:        btst    d1,(a6)            ;waiting for the blitter ...
  214.         bne.s    .WB
  215.  
  216.         move.l    d4,$40-2(a6)        ;writing to the blitter regs as fast as possible.
  217.         move.l    d2,$62-2(a6)
  218.         move.l    a0,$48-2(a6)
  219.         move.w    d0,(a1)+
  220.         move.l    a0,(a1)+        ;shit-word buffer pt.
  221.         move.w    d3,(a1)
  222.         rts
  223.  
  224. ; ------------- oktant-table --------------------------------------------
  225.  
  226. .oktants:    dc.b    SML+1,SML+1+$40
  227.         dc.b    SML+17,SML+17+$40
  228.         dc.b    SML+9,SML+9+$40
  229.         dc.b    SML+21,SML+21+$40
  230.  
  231. ***************************************************
  232. *** Main Loop                    ***
  233. ***************************************************
  234.  
  235. Main:        move.l    $04(a5),d0
  236.         and.l    #$1ff00,d0
  237.         cmp.l    #150*256,d0
  238.         bne.s    Main
  239.  
  240. .Wait:        move.l    $04(a5),d0
  241.         and.l    #$1ff00,d0
  242.         cmp.l    #151*256,d0
  243.         bne.s    .Wait
  244.  
  245.         bsr.s    TestMousePos        ;This is the MAIN routine!
  246.  
  247.         btst    #6,$bfe001
  248.         bne.s    Main
  249.  
  250. .WB:        btst    #6,2(a5)
  251.         bne.s    .WB
  252.         rts
  253.  
  254. ***************************************************
  255. *** Test Mouse Pos                ***
  256. ***************************************************
  257.  
  258. TestMousePos:    lea    Koords(pc),a0        ;Polygon Ptr
  259.         movem.w    MousePos(pc),d4-d5    ;X,Y Coord of Point
  260.         bsr.s    PointInPolygon
  261.         tst.w    d0            ;Test Flag
  262.         beq.s    .InPolygon        ;if d0 = 0 -> inside!
  263.  
  264. .Beep:        move.w    #$f00,$dff180        ;Point outside polygon
  265.         rts
  266.  
  267. .InPolygon:    move.w    #$0f0,$dff180        ;Point inside polygon
  268. .Exit:        rts
  269.  
  270. ***************************************************
  271. *** Point in Polygon Routine            ***
  272. ***************************************************
  273.  
  274. ;a0 = Ptr on Polygon Coordinate Lis (Polygon Clockwise!)
  275. ;d4 = X-Coord of point
  276. ;d5 = Y-Coord of point
  277. ;-> d0 <> 0 when point outside; d0 = 0 when point inside
  278.  
  279. PointInPolygon:    move.w    (a0)+,d7        ;Amount of polygon lines-1
  280.  
  281. .PolygonLoop:    movem.w    (a0)+,d0-d3        ;Get Line Coords
  282.  
  283.         sub.w    d0,d2            ;(x2-x1)
  284.         move.w    d5,d6            ;save y
  285.         sub.w    d1,d6            ;(y-y1)
  286.         muls    d6,d2            ;(y-y1)*(x2-x1)
  287.  
  288.         sub.w    d1,d3            ;(y2-y1)
  289.         move.w    d4,d6            ;save x
  290.         sub.w    d0,d6            ;(x-x1)
  291.         muls    d6,d3            ;(y2-y1)*(x-x1)
  292.  
  293.         sub.l    d3,d2            ;(y-y1)*(x2-x1)-(y2-y1)*(x-x1)
  294.         bmi.s    .OutOfPolygon        ;if neg-> outside
  295.  
  296.         dbf    d7,.PolygonLoop
  297.         moveq    #0,d0            ;set inside-flag
  298.         rts
  299.  
  300. .OutOfPolygon:    moveq    #-1,d0            ;set outside-flag
  301.         rts
  302.  
  303. *** Polygon Structure ***
  304.  
  305. Koords:        dc.w    5-1            ;Polygon with 5 lines
  306.         dc.w    55,1,100,30        ;1. lines
  307.         dc.w    100,30,80,90        ;2. lines
  308.         dc.w    80,90,20,80        ;3. lines
  309.         dc.w    20,80,10,30        ;4. lines
  310.         dc.w    10,30,55,1        ;5. lines
  311.  
  312. ***************************************************
  313. *** Level3Int (Mouse-Routine)            ***
  314. ***************************************************
  315.  
  316. MouseRoutine:    movem.l    d0-d4/a0/a5,-(sp)
  317.  
  318.         lea    $dff000,a5
  319.         btst    #5,$1e+1(a5)        ;VBI ? (INTREQR+1)
  320.         beq.s    .Exit            ;no-> Exit
  321.  
  322.         move.w    #$0020,$9c(a5)        ;Clear VBI Bit
  323.  
  324.         lea    MousePos(pc),a0
  325.         move.w    (a0)+,d0
  326.         move.w    (a0)+,d1
  327.         move.w    $0a(a5),d2
  328.         move.w    d2,d3
  329.         sub.b    1(a0),d2
  330.         move.b    d2,d4
  331.         ror.w    #8,d2
  332.         sub.b    (a0),d2
  333.         move.w    d3,(a0)
  334.         ext.w    d4
  335.         add.w    d4,d0
  336.         bgt.s    .Right
  337.         moveq    #0,d0
  338.         bra.s    .Up
  339. .Right:        cmp.w    #MouseClipX,d0
  340.         blt.s    .Up
  341.         move.w    #MouseClipX,d0
  342.  
  343. .Up:        ext.w    d2
  344.         add.w    d2,d1
  345.         bgt.s    .Down
  346.         moveq    #0,d1
  347.         bra.s    .SetSpr
  348. .Down:        cmp.w    #MouseClipY,d1
  349.         blt.s    .SetSpr
  350.         move.w    #MouseClipY,d1
  351.  
  352. ;\
  353. ; >- Now set the Sprite 
  354. ;/
  355.  
  356. .SetSpr:    movem.w    d0-d1,-(a0)        ;Set X,Y
  357.         lea    MouseSpr(pc),a0        ;Sprite Structure Ptr
  358.         add.w    #128,d0
  359.         add.w    #42,d1
  360.         move.w    d1,d3
  361.         addq.w    #SpriteHigh,d3
  362.         moveq    #0,d4
  363.         lsl.w    #8,d1
  364.         addx.b    d4,d4
  365.         lsl.w    #8,d3
  366.         addx.b    d4,d4
  367.         or.w    d4,d3
  368.         lsr.w    #1,d0
  369.         addx.b    d3,d3
  370.         or.w    d0,d1
  371.         move.w    d1,(a0)+
  372.         move.w    d3,(a0)
  373. .Exit:        movem.l    (sp)+,d0-d4/a0/a5
  374.         rte
  375.  
  376. MousePos:    dc.w    0,0            ; Don't change the order!
  377. OldMove:    dc.w    0            ;/
  378.  
  379. ***************************************************
  380. *** Datas                    ***
  381. ***************************************************
  382.  
  383. NCList:
  384. MouseSprite:    dc.l    $01200000,$01220000,$01240000,$01260000
  385.         dc.l    $01280000,$012a0000,$012c0000,$012e0000
  386.         dc.l    $01300000,$01320000,$01340000,$01360000
  387.         dc.l    $01380000,$013a0000,$013c0000,$013e0000
  388.  
  389.         dc.l    $008e2981,$009029c1,$00920038,$009400d0
  390.         dc.l    $01020000,$01040000,$01080000,$010a0000
  391.         dc.l    $01000200,$01a20ff0
  392.  
  393. PlanePtr:    dc.l    $00e00000,$00e20000
  394.         dc.l    $01001200
  395.  
  396.         dc.l    $01800000,$018200ff
  397.         dc.l    -2
  398.  
  399. MouseSpr:    dc.w    0,0
  400.         dc.w    $8000,$0000
  401.         dc.w    0,0
  402.  
  403. ***************************************************
  404. *** BSS Data Segment                ***
  405. ***************************************************
  406.  
  407.         section    b,bss_c
  408.  
  409. Plane:        ds.b    PlaneLen
  410.  
  411.         END
  412.  
  413.